/* NOTICE
 
    Jim - the Java Image Manager, copyright (c) 2005 - 2007 Grant Gardner 
 
    Jim is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Jim is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
    In addition, as a special exception, you are permitted to link this code
    with the 3rd party libraries required to compile this file and to
    distribute a linked combination including them. You must obey the
    GNU General Public License in all respects for all of the code except for
    those 3rd party libraries that are licenced under terms incompatible with the
    GNU General Public License.  
 
 
 NOTICE */

package au.com.lastweekend.jim.experimental;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * 1. Scale the area of all the rectangles so that the total area of the input rectangles equals that of the layout rectangle.<br>
 * 2. Create a new empty strip, the current strip.<br>
 * 3. Add the next rectangle to the current strip, recomputing the height of the strip based on the area of all the rectangles
 * within the strip, and then recomputing the width of each rectangle.<br>
 * 4. If the average aspect ratio of the current strip has increased as a result of adding the rectangle in step 3, remove the
 * rectangle pushing it back onto the list of rectangles to process and go to step 2.<br>
 * 5. If all the rectangles have been processed, stop. Else, go to step 3.
 * 
 * The primary difference is in step 3 where the rectangle dimensions are computed for the current strip. Instead of computing
 * dimensions to exactly match the requested area of each rectangle, the dimensions must be computed to be integral multiples of
 * the elemental input object size. With the original ST, the height of the strip is calculated with
 * (total-area-of-rectangles-in-strip / width-of-layout-box). But with QST the height is calculated by taking the height as
 * calculated by ST, and increasing it to the next highest multiple of the input object height. Similarly, the width of each
 * rectangle is grown or shrunk to the next multiple of the input object width. It is shrunk if the resulting rectangle dimensions
 * would be large enough to accommodate the number of requested objects – otherwise, it is grown as needed.
 * 
 * After this change, there is a remaining problem which is that the resulting treemap will have a ragged right edge since some of
 * the rectangles will have grown in width more than others, and there can be differing numbers of rectangles on each row. Thus,
 * there needs to be a concluding evening step that evens out the ragged right edge. The simplest way to do this is to add enough
 * space to the width of the right-most rectangle in each strip so that the resulting width of the total strip matches the width of
 * the largest strip.
 * 
 * This simple approach to evening can result in some rectangles being expanded significantly with the result that there will be a
 * significant amount of empty space when the objects are laid out in those rectangles. A simple solution is to distribute the
 * extra space through all the rectangles in the strip.
 * 
 * @author ggardner
 * @version $Id: org.eclipse.jdt.ui.prefs,v 1.1 2006/02/04 00:31:36 ggardner Exp $
 */
@SuppressWarnings("PMD")
public class QuantumStripTreemap {

    private static final org.apache.log4j.Logger LOG = org.apache.log4j.Logger.getLogger(QuantumStripTreemap.class);

    public class Strip {

        private static final boolean CHECK_WASTED_SPACE = true;

        private List<TreemapNode> _nodes = new ArrayList<TreemapNode>();

        private int _width;
        private List<Double> _currentWidths = new ArrayList<Double>();;
        private List<Double> _nextWidths = new ArrayList<Double>();
        private double _currentAspect = Double.NEGATIVE_INFINITY;
        private int _totalArea;

        public Strip(int width) {

            _width = width;
            // Always have a temporary width to play with...
            _nextWidths.add(0.0);
        }

        public boolean addNodeIfStripLayoutIsBetter(TreemapNode nextNode) {

            double averageAspect = calculateWidths(_nextWidths, nextNode);

            if (averageAspect >= _currentAspect) {
                _nodes.add(nextNode);
                _totalArea = _totalArea + nextNode.nodeCount();
                _currentAspect = averageAspect;
                List<Double> temp = _currentWidths;
                _currentWidths = _nextWidths;
                _nextWidths = temp;
                _nextWidths.add(0.0);
                _nextWidths.add(0.0);
                return true;
            }

            return false;

        }

        /**
         * Returns the averageAspect
         * 
         * @param nextWidths -
         *            list to fill with widths, will be quantized before returning
         * @param nextNode
         * @return
         */
        private double calculateWidths(List<Double> nextWidths, TreemapNode nextNode) {

            int tempArea = _totalArea + nextNode.nodeCount();

            // Round up height to nearest int.
            double suggestedHeight = Math.ceil((double) tempArea / (double) _width);
            double maxHeight = 1.0;

            double totalAspect = 0;
            double totalWidth = 0;

            for (int i = 0; i <= _nodes.size(); i++) {
                TreemapNode stripNode;
                if (i < _nodes.size())
                    stripNode = _nodes.get(i);
                else {
                    stripNode = nextNode;
                }

                int cellArea = stripNode.nodeCount();
                double width = cellArea / suggestedHeight;

                // Quantize..
                width = Math.max(Math.floor(width), 1.0);
                nextWidths.set(i, width);

                maxHeight = Math.max(maxHeight, Math.ceil(cellArea / width));

                totalWidth += width;

                totalAspect += aspect(cellArea, width);

            }

            if (totalWidth > _width) {
                LOG.debug("Rejecting " + nextNode + " as overwidth by " + (totalWidth - _width));
                return Double.NEGATIVE_INFINITY;
            }
            // If we end up over width, return negative aspect, ie reject the
            // nextNode.
            // Can get more sophisticated about that later on.

            if (CHECK_WASTED_SPACE) {
                // Returns negative. A bigger number is better
                return tempArea - (_width * maxHeight);
            }

            return totalAspect / (_nodes.size() + 1);

        }

        public int size() {

            return _nodes.size();
        }

        public void layoutStrip(QSTLayout result, int x) {

            int y = result.getY() + result.getHeight();
            int maxSubLayoutHeight = 0;

            for (int i = 0; i < size(); i++) {

                TreemapNode stripNode = _nodes.get(i);

                int nodeWidth = _currentWidths.get(i).intValue();

                QSTLayout subLayout = layout(stripNode, x, y, nodeWidth);

                maxSubLayoutHeight = Math.max(maxSubLayoutHeight, subLayout.getHeight());

                result.addSubLayout(subLayout);

                x = x + nodeWidth;

            }

            result.addStripHeight(maxSubLayoutHeight);

        }

    }

    public class QSTLayout {

        private TreemapNode _node;
        private int _x;
        private int _y;
        private int _width;
        private int _height = 0;
        private List<QSTLayout> _subLayouts = new ArrayList<QSTLayout>();

        public QSTLayout(TreemapNode node, int x, int y, int width) {

            _node = node;
            _x = x;
            _y = y;
            _width = width;

        }

        public int getWidth() {

            return _width;
        }

        public int getHeight() {

            return _height;
        }

        public void addSubLayout(QSTLayout subLayout) {

            _subLayouts.add(subLayout);

        }

        public void addStripHeight(int stripHeight) {

            _height += stripHeight;

        }

        public TreemapNode getNode() {

            return _node;
        }

        public List<QSTLayout> getSubLayouts() {

            return _subLayouts;
        }

        public int getX() {

            return _x;
        }

        public int getY() {

            return _y;
        }

        @Override
        public String toString() {

            StringBuffer buff = new StringBuffer(_node.toString());
            buff.append(": area=");
            buff.append(_node.nodeCount());
            buff.append(": x=");
            buff.append(_x);
            buff.append("; y=");
            buff.append(_y);
            buff.append("; w=");
            buff.append(_width);
            buff.append("; h=");
            buff.append(_height);
            buff.append("\n");
            for (QSTLayout subLayout : _subLayouts) {
                buff.append(subLayout.toString());
            }
            return buff.toString();
        }

        public TreemapNode[][] toArray() {

            TreemapNode[][] result = new TreemapNode[_width][_height];
            fillArray(result);
            return result;
        }

        private void fillArray(TreemapNode[][] result) {

            if (_subLayouts.isEmpty()) {
                if (result[_x][_y] != null) {
                    throw new IllegalStateException("Trying to add " + _node + " at  (" + _x + "," + _y + ") already used by "
                            + result[_x][_y]);

                }
                result[_x][_y] = _node;
            } else {
                for (QSTLayout subLayout : _subLayouts) {
                    subLayout.fillArray(result);
                }
            }
        }

    }

    public interface TreemapNode {

        ListIterator<TreemapNode> getChildrenIterator();

        int nodeCount();

    }

    public QSTLayout layout(TreemapNode node, final int initialX, final int initialY, final int width) {

        // Layout a node starting at x,y for the given width.
        // Returns a result including the height and a list of subrectangles.
        QSTLayout result = new QSTLayout(node, initialX, initialY, width);

        ListIterator<TreemapNode> childIterator = node.getChildrenIterator();

        if (!childIterator.hasNext()) {
            result.addStripHeight(1);
            return result;
        }

        // TODO Optimize for leaf nodes (nodeCount() = 1);
        int stripcount = 0;
        Strip currentStrip = new Strip(width);

        while (childIterator.hasNext()) {

            TreemapNode nextNode = childIterator.next();

            if (currentStrip.addNodeIfStripLayoutIsBetter(nextNode)) {
                if (childIterator.hasNext()) {
                    // More nodes to try..
                    continue;
                }
            } else {
                // Reject the node for this strip
                childIterator.previous();
            }

            // Write the strip
            currentStrip.layoutStrip(result, initialX);
            currentStrip = new Strip(width);
            stripcount++;
        }

        return result;
    }

    private static double aspect(int area, double width) {

        double aspect = ((width * width)) / area;

        return Math.min(aspect, 1.0 / aspect);
    }
}
